package algorithm.leetcode.I101to200;

import java.util.Stack;

/**
 * 逆波兰表达式求值
 *
 * 从逻辑表达式转换为逆波兰表达式才叫难,可以百度搜索下流程图
 */

public class Q150 {

    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();

        for (String token : tokens) {
            if ("+".equals(token)) {
                stack.push(stack.pop() + stack.pop());
            }
            else if ("-".equals(token)) {
                stack.push(-stack.pop()+stack.pop());
            }
            else if ("*".equals(token)) {
                stack.push(stack.pop() * stack.pop());
            }
            // 除法不能用倒数去省略写,因为存在分母为0的情况
            else if ("/".equals(token)) {
                int later = stack.pop();
                int former = stack.pop();
                stack.push(former/later);
            }
            else {
                stack.push(Integer.parseInt(token));
            }
        }
        
        return stack.pop();
    }

    public static void main(String[] args) {
        Q150 q150 = new Q150();
        q150.evalRPN(new String[]{"2","1","+","3","*"});
    }

}
